// This isn't a real header. It just gives me a place to hang
// doxygen's \mainpage comment.
namespace std {
/// \mainpage A minimal std::range<Iter>
/// \xmlonly <document-number>N????=12-0???</document-number> \endxmlonly
/// \author Jeffrey Yasskin <jyasskin@google.com>
/// \author Source at http://code.google.com/p/cxx1y-range/
///
/// \section overview Overview
///
/// Ranges are ubiquitous in programs that use STL algorithms, but
/// they're always written as adjacent iterator arguments, which makes
/// them hard to use. Several groups have proposed a new set of range
/// concepts that would allow ranges to be passed around as single
/// objects.  Two notable examples are the <a
/// href="http://www.boost.org/libs/range/doc/html/index.html">Boost.Range</a>
/// library and <a
/// href="http://www.informit.com/articles/printerfriendly.aspx?p=1407357">Andrei
/// Alexandrescu's range concepts</a> <a
/// href="http://www.d-programming-language.org/phobos/std_range.html">in
/// D</a>.
///
/// This paper, and the library at <a
/// href="http://code.google.com/p/cxx1y-range/">http://code.google.com/p/cxx1y-range/</a>,
/// attempt to take these ideas and produce a minimal library that's
/// useful today and is suitable for standardization.
///
/// \section inventions Changes from existing libraries
///
/// This library makes certain changes from the existing range
/// libraries:
///
/// Boost's range library focuses on defining a set of Range concepts
/// that allow Containers to be Ranges.  Because Containers are
/// heavy-weight, this forces Boost to use references for all of their
/// uses of Ranges, including Ranges that are captured by Range
/// Adapters.  This worked fine in C++98, where users couldn't name
/// the types of the Range Adapters in order to declare local
/// variables, but with C++11's \c auto keyword, users can now save
/// adapted ranges. Since Boost's adapted ranges capture references to
/// their arguments, which can be temporaries, this is no longer a
/// safe design.
///
/// This paper makes the opposite choice: it defines a concrete type
/// and no concepts, and the concrete type is a lightweight view into
/// a container.  This implies that algorithms can't treat Ranges and
/// Containers interchangeably, but there are ways around this, which
/// I explore below.  Of the Boost types, this paper's \c std::range
/// is most like <a
/// href="http://www.boost.org/doc/libs/1_48_0/libs/range/doc/html/range/reference/utilities/iterator_range.html"><code>boost::iterator_range</code></a>.
///
/// Andrei Alexandrescu's range concepts provide a complete
/// replacement for iterators.  However, they require that the whole
/// machinery be adopted at once, which isn't appropriate for a
/// widely-used language like C++.  This paper's \c std::range
/// allows users to program against the Range concepts while still
/// accepting data from iterator-oriented containers.
///
/// This paper's \c range<> omits Alexandrescu's
/// <code>ForwardRange.save()</code> operation, on the theory that
/// it's just a type assertion for most ForwardRanges (since they
/// provide a full-featured copy operation), so most algorithms would
/// forget to call \c save().  This would introduce bugs when those
/// algorithms were used with the rare ForwardRange that could take
/// advantage of it to save work on plain copies.  It's better to omit
/// the optimization than to lay traps.
///
/// Like the D ranges, but unlike the STL's iterators, this paper's \c
/// range uses the same names for O(1) and O(N) operations.  Some
/// reviewers found the O(N) names (\c advance and \c shorten)
/// confusing, and with \c static_assert(), users can now check the
/// category explicitly if they're concerned.  The one operation we
/// didn't make work for all categories was <code>operator[]</code> on
/// the theory that indexing is much more likely to indicate a
/// programmer mistake than other operations.
///
/// This proposal allows negative indices for indexing operations,
/// following the lead of several scripting languages.  Neither of the
/// earlier range implementations does this for arbitrary ranges, but
/// D does allow users to <a
/// href="http://www.d-programming-language.org/arrays.html#array-length">offset
/// from the end</a> of a random-access range.
///
/// \section writing_algorithms How to write algorithms that use ranges
///
/// As mentioned above, you can't simply write an algorithm that takes
/// either Containers or <code>std::range<></code>s and treats them
/// interchangeably:
/// \code
/// template<typename T>
/// void my_algorithm(T argument) {  // Copies any containers.
///   while (!argument.empty()) {
///     process(argument.front());
///     // Fails on vectors; destructive on deques; fine on ranges:
///     argument.pop_front();
///   }
/// }
/// \endcode
///
/// The limits of template argument deduction make it inconvenient to
/// take a \c std::range explicitly:
/// \code
/// template<typename Iter>
/// void my_algorithm(std::range<Iter> argument) {
///   while (!argument.empty()) {
///     process(argument.front());
///     argument.pop_front();
///   }
/// }
///
/// void user() {
///   ContainerT my_container;
///   // Fails! std::range<ContainerT::iterator> has an implicit
///   // conversion from ContainerT, but because the type of the
///   // explicit argument doesn't match "std::range<*>", the
///   // compiler can't deduce the template argument.
///   my_algorithm(my_container);
///
///   // Works, but verbose:
///   my_algorithm(std::make_range(my_container));
/// }
/// \endcode
///
/// The best option seems to be for algorithms that want to take
/// either containers or ranges, and use ranges internally, to take
/// their parameter by \c T& or <code>const T&</code> and use
/// make_range() to build a range out of it explicitly:
/// \snippet range_run_test.cc algorithm using range
///
/// \par
/// By storing the result of \c make_range() in an \c auto variable,
/// we allow authors of future range types to overload it as the
/// identity operation on types that are already ranges.
///
/// \par
/// The one case where taking \c std::range explicitly seems to make
/// sense is \c range<T*>.  If an algorithm needs contiguous
/// iterators, this can allow its authors to avoid making it a
/// template:
/// \snippet range_run_test.cc algorithm using ptr_range
///
/// \sa std::range
///
/// \section misc Miscellaneous other changes
///
/// Certain other pieces of the library should change to make life
/// easier for \c range<>.
///
///  - \c std::begin(), \c std::end(), and \c std::distance should
///    become \c constexpr.
///  - We need a \c contiguous_iterator_tag to let \c range<T*> safely
///    construct from user-defined types that control contiguous
///    sequences of objects.
///  - The <code>*_upto</code> methods could take advantage of a
///    <code>std::advance_upto(it, n, end)</code> algorithm on plain
///    iterators, which advances the iterator either n increments or
///    to 'end', whichever comes first.
///
/// \section future Future work
///
/// Many functions will be able to take either Ranges or Containers as
/// arguments.  We should work out what concept their argument
/// follows.  "Iterable"?
///
/// Versions of all of the algorithms should be added that accept
/// ranges.  While it would be possible to make them take \c
/// std::range<> itself, a set of Range concepts will likely work
/// better in the long run, leaving \c std::range<> as an interface
/// between the iterator and range worlds.
///
/// <a
/// href="http://www.boost.org/doc/libs/1_48_0/libs/range/doc/html/range/reference/adaptors/introduction.html">Boost's
/// adapters</a> are a great idea and should be added to the standard.
///
/// Infinite ranges could be defined, whose \c empty() method returns
/// \c std::false_type.
///
/// We should figure out how to fit OutputIterators into the
/// range framework.
///
/// A collection of \c any_range types would be useful.
///
/// \sa \ref todo
}
